#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <pthread.h>
#include "yield.h"
#include "rbtree.h"

//pthread_mutex_t mutex;
/* Arboles Rojo-Negro.
 * Son abbs balanceados, as�que la bsqueda es siempre O(lg(n))!
 */

/* Esta secci� hay que modificarla para tener �boles de distintas cosas. 
 * El tipo alfa es el tipo de los nodos del �bol.  Debe tener: 
 *  - un constructor (que puede no hacer nada), que no tome nada y devuelva un 
 *    alfa inicializado. 
 *  - un destructor (que puede no hacer nada), que tome un alfa y devuelva 
 *    void, sin precondiciones. 
 *  - un comparador que tome dos alfa y devuelva un int, que indique <0, 0 
 *    �>0 si el segundo alfa es respectivamentes menor, igual o mayor que 
 *    el primero. 
 *  - un asignador, que actualice los datos de un alfa segn otro.  Debe tomar 
 *    dos alfa, el primero destino y el segundo origen, y devolver void. 
 *  - Si se quiere que funcione rbtshow, hay que proveer un mostrador, que 
 *    tome un alfa y devuelva un char* de una representaci� del alfa que no 
 *    ocupe m� de un rengl�, sin el \n.  El char* debe estar mallocado, pues 
 *    ser�freeado al finalizar. 
 */

#include "ieentry.h" 

alfa* (*alfanew)(void) = ieentry_new; /* constructor */

void (*alfadestroy)(alfa* este) = ieentry_destroy; /* destructor */

int (*alfacompare)(alfa* uno, alfa* dos) = iekey_compare; /* comparador */

void (*alfaasign)(alfa* dest, alfa* src) = ieentry_copy; /* asignador */

char *(*alfashow)(alfa* este) = ieentry_show; /* Mostrador */

static struct rbtree* __gimmeanode(void);
static struct rbtree* __rbtinsert(struct rbtree* este, alfa* a);
static void __rbtshow(const struct rbtree* este, char* pref);
static void __rbtassert(const struct rbtree* este);
pthread_mutex_t mutex;
/* Crea e inicializa un �bol Rojo-Negro
 */
struct rbtree* rbtnew(void)
{
    pthread_mutex_init(&mutex, NULL);
    return NULL;
}

/* Reserva memoria para un nodo m�, e inicializa el nodo.
 *  Esta es una funci� interna. */
static struct rbtree* __gimmeanode(void)
{
    
    struct rbtree* newtree;
    newtree = (struct rbtree*) malloc (sizeof (struct rbtree));
    newtree -> elem = alfanew();
    newtree -> left = NULL;
    newtree -> right = NULL;
    newtree -> color = rojo;
    return newtree;
}

/* Libera la memoria reservada para este �bol y sus hijos
 */
struct rbtree* rbtdestroy(struct rbtree* este)
{
    __rbtassert(este);
    if (este -> left)
        este -> left = rbtdestroy (este -> left);
    if (este -> right)
        este -> right = rbtdestroy (este -> right);
    alfadestroy(este -> elem);
	free(este);

	pthread_mutex_destroy(&mutex);

    return NULL;
}



/* Inserta un nuevo nodo en el �bol, manteniendo abb
 * Si ya est�en el �bol, lo reemplaza por el dado.
 * Primero va la funci� interna, que no pinta la ra� de negro, y luego la
 * funci� pblica.
 */
static struct rbtree* __rbtinsert(struct rbtree* este, alfa* a)
{
    
    int caso;
    struct rbtree* newtree, *bufa, *bufb;
    
    
    
    if (este)
    {
        caso = alfacompare(este -> elem, a);
        if (caso == 0)
            alfaasign(este -> elem, a);
        else if (caso < 0)
        {
            if (este -> left == NULL)
            {
                newtree = __gimmeanode();
                alfaasign(newtree -> elem, a);
                este -> left = newtree;
            }
            else
            {
                este -> left = __rbtinsert(este -> left, a);
                /*    b/\        r/\
                 *   r/\ ^      b/\/\b
                 *  r/\ ^  =>   ^ ^^ ^
                 *  ^  ^ 
                 */
		/*pthread_mutex_lock(&mutex);*/
		
                if (este -> left -> color == rojo &&
                 este -> left -> left != NULL &&
                 este -> left -> left -> color == rojo)
                {
		    yield0();
                    bufa = este -> left;
                    bufb = bufa -> right;
                    bufa -> right = este;
                    bufa -> right -> left = bufb;
                    bufa -> left -> color = negro;
                    este = bufa;
		    
                }
                /*    b/\        r/\
                 *   r/\ ^      b/\/\b
                 *   ^ /\r  =>  ^ ^^ ^
                 *    ^  ^
                 */
                else if (este -> left ->color == rojo &&
                 este -> left -> right != NULL &&
                 este -> left -> right -> color == rojo)
                {
		    yield0();
                    bufa = este -> left -> right;
                    bufb = bufa -> left;
                    bufa -> left = este -> left;
                    bufa -> left -> right = bufb;
                    bufb = bufa -> right;
                    bufa -> right = este;
                    bufa -> right -> left = bufb;
                    bufa -> left -> color = negro;
                    este = bufa;
                }
		/*pthread_mutex_unlock(&mutex);*/
            }
        }
        else if (caso > 0)
        {
            if (este -> right == NULL)
            {
	    	yield0();
                newtree = __gimmeanode();
                alfaasign(newtree -> elem, a);
                este -> right = newtree;
            }
            else
            {
                este -> right = __rbtinsert(este -> right, a);
                /*      /\b         r/\
                 *     ^ /\r   =>  b/\/\b
                 *     r/\ ^       ^ ^^ ^
                 *     ^  ^
                 */
		/*pthread_mutex_lock(&mutex);*/
                if (este -> right -> color == rojo &&
                 este -> right -> left != NULL &&
                 este -> right -> left -> color == rojo)
                {
		    yield0();
                    bufa = este -> right -> left;
                    bufb = bufa -> right;
                    bufa -> right = este -> right;
                    bufa -> right -> left = bufb;
                    bufb = bufa -> left;
                    bufa -> left = este;
                    bufa -> left -> right = bufb;
                    bufa -> right -> color = negro;
                    este = bufa;
                }
                /*      /\b        r/\
                 *     ^ /\r   => b/\/\b
                 *      ^ /\r     ^ ^^ ^
                 *       ^  ^
                 */
                else if (este -> right -> color == rojo &&
                 este -> right -> right != NULL &&
                 este -> right -> right -> color == rojo)
                {
		    yield0();
                    bufa = este -> right;
                    bufb = bufa -> left;
                    bufa -> left = este;
                    bufa -> left -> right = bufb;
                    bufa -> right -> color = negro;
                    este = bufa;
                }
		/*pthread_mutex_unlock(&mutex);*/
             }
        }
    }
    else
    {
        newtree = __gimmeanode();
        alfaasign (newtree -> elem, a);
        este = newtree;
    }
 
    
    
    return este;
    
}

/* Remueve el nodo a del �bol, manteniendo abb.  Si a no pertenece al
 * �bol, no lo remueve.
 */
struct rbtree* rbtremove (struct rbtree* este, alfa* a)
{
    /* funcion no definida */
    a=a;
    return este;
}


struct rbtree* rbtinsert(struct rbtree* este, alfa *a)
{	
    #ifdef __DEBUG
    pthread_mutex_lock(&mutex);
    #endif
    __rbtassert(este);
    este = __rbtinsert(este, a);
    yield0();
    este -> color = negro;
    #ifdef __DEBUG
    pthread_mutex_unlock(&mutex);
    #endif
    return este;

}


/* Indica si el elemento A se encuentra en el �bol.  Si se encuentra, se
 * coloca una copia del contenido en el �bol en RES.
 */
int rbtget(const struct rbtree* este, alfa* a, alfa* res)
{
	
    int caso;
	#ifdef __DEBUG
	pthread_mutex_lock(&mutex);
	#endif
    __rbtassert(este);
	#ifdef __DEBUG
	pthread_mutex_unlock(&mutex);
	#endif
    while (este)
    {
    	yield0();
        caso = alfacompare(este -> elem, a);
        if (caso == 0)
        {
            if (res)
                alfaasign(res, este -> elem);
            return 1;
	    
        }
        else if(caso < 0)
            este = este -> left;
        else if(caso > 0)
            este = este -> right;
    }
    return 0;
}


/* Saca por stdout una representaci� del �bol.
 * Usa la siguiente funci� interna, para hacer recursi� sobre la estructura
 */
static void __rbtshow(const struct rbtree* este, char* pref)
{
    char buf[30000];
    if (este)
    {
        printf("%s%c %s\n",pref,(este->color==rojo?'r':'n'), alfashow (este -> elem));
        if (este -> left)
 	{
	    yield0();
            strcpy (buf, pref);
            strcat (buf, "|");
            printf("%sIzquierda:\n", pref);
            __rbtshow(este -> left, buf);
            printf("%s`\n", pref);
        }
        if (este -> right)
        {
	    yield0();
            strcpy (buf, pref);
            strcat (buf, "|");
            printf("%sDerecha:\n", pref);
            __rbtshow(este -> right , buf);
            printf("%s`\n",pref);
        }
    }
}


void rbtshow(const struct rbtree* este)
{
    char buf[30000]="";
    __rbtshow(este, buf);
}


/* Comprueba que nodo rojo => hijos negros.
 * Notar que hay mas condiciones de consistencia.
 */
void __rbtassert(const struct rbtree* este)
{
	if (este) {
		assert(este->color==negro || 
			((!este->left || este->left->color==negro) 
				&& (!este->right || este->right->color==negro)));
		__rbtassert(este->left);
		__rbtassert(este->right);
	}
}

